Given a set $\Pi$ of permutation patterns of length at most $k$, we presentan algorithm for building $S_{\le n}(\Pi)$, the set of permutations of lengthat most $n$ avoiding the patterns in $\Pi$, in time $O(|S_{\le n - 1}(\Pi)|\cdot k + |S_{n}(\Pi)|)$. Additionally, we present an $O(n!k)$-time algorithmfor counting the number of copies of patterns from $\Pi$ in each permutation in$S_n$. Surprisingly, when $|\Pi| = 1$, this runtime can be improved to $O(n!)$,spending only constant time per permutation. Whereas the previous bestalgorithms, based on generate-and-check, take exponential time per permutationanalyzed, all of our algorithms take time at most polynomial per outputtedpermutation. If we want to solve only the enumerative variant of each problem, computing$|S_{\le n}(\Pi)|$ or tallying permutations according to $\Pi$-patterns, ratherthan to store information about every permutation, then all of our algorithmscan be implemented in $O(n^{k+1}k)$ space. Using our algorithms, we generated $|S_5(\Pi)|, \ldots, |S_{16}(\Pi)|$ foreach $\Pi \subseteq S_4$ with $|\Pi| > 4$, and analyzed OEIS matches. Weobtained a number of potentially novel pattern-avoidance conjectures. Our algorithms extend to considering permutations in any set closed understandardization of subsequences. Our algorithms also partially adapt toconsidering vincular patterns.
展开▼
机译：给定一组最大长度为$ k $的排列模式\\ Pi $，我们提出了一种构建$ S _ {\ le n}（\ Pi）$的算法，该数组的最大长度为$ n $的排列避免了模式$ \ Pi $，时间为$ O（| S _ {\ le n-1}（\ Pi）| \ cdot k + | S_ {n}（\ Pi）|）$。此外，我们提出了一种$ O（n！k）$时间算法，用于计算$ S_n $中每个排列中$ \ Pi $中的模式副本数。令人惊讶的是，当$ | \ Pi | = 1 $，此运行时可以提高到$ O（n！）$，每个排列只花费恒定的时间。之前的基于生成和检查的最佳算法，每个排列需要花费指数时间，而我们的所有算法每个输出排列最多都需要多项式的时间。如果我们只想解决每个问题的枚举变体，则根据$ \ Pi $模式计算$ | S _ {\ le n}（\ Pi）| $或计数排列，而不是存储有关每个排列的信息，则所有我们的算法可以在$ O（n ^ {k + 1} k）$空间中实现。使用我们的算法，我们生成了$ | S_5（\ Pi）|，\ ldots，| S_ {16}（\ Pi）| $ foreach $ \ Pi \ subseteq S_4 $和$ | \ Pi | > 4 $，并分析OEIS匹配。我们获得了许多潜在的新颖的避免模式猜想。我们的算法扩展为考虑子序列的任何集合封闭式理解中的置换。我们的算法还部分适应了考虑到的葡萄酒图案。
展开▼
